#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <omp.h>

#define V 1000000  // Количество вершин в графе
#define E 5000000  // Примерное количество рёбер в графе

typedef struct Edge {
    int src, dest, weight;
} Edge;

typedef struct Graph {
    int numVertices, numEdges;
    Edge* edges;
} Graph;

Graph* createGraph(int numVertices, int numEdges) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->numEdges = numEdges;
    graph->edges = (Edge*)malloc(numEdges * sizeof(Edge));
    return graph;
}

void generateRandomGraph(Graph* graph) {
    srand(time(0));
    #pragma omp parallel for
    for (int i = 0; i < graph->numEdges; i++) {
        graph->edges[i].src = rand() % V;
        graph->edges[i].dest = rand() % V;
        graph->edges[i].weight = rand() % 100 + 1;  // Случайный вес от 1 до 100
    }
}

int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void unionSets(int parent[], int x, int y) {
    int xroot = find(parent, x);
    int yroot = find(parent, y);
    if (xroot != yroot)
        parent[xroot] = yroot;
}

int compare(const void* a, const void* b) {
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;
    return edge1->weight - edge2->weight;
}

void kruskalMST(Graph* graph) {
    int parent[V];
    for (int i = 0; i < V; i++)
        parent[i] = -1;

    qsort(graph->edges, graph->numEdges, sizeof(graph->edges[0]), compare);

    int mstWeight = 0;
    #pragma omp parallel for
    for (int i = 0; i < graph->numEdges; i++) {
        int root1 = find(parent, graph->edges[i].src);
        int root2 = find(parent, graph->edges[i].dest);

        if (root1 != root2) {
            #pragma omp critical
            {
                printf("Edge %d-%d weight %d\n", graph->edges[i].src, graph->edges[i].dest, graph->edges[i].weight);
                mstWeight += graph->edges[i].weight;
                unionSets(parent, root1, root2);
            }
        }
    }

    printf("Total weight of MST: %d\n", mstWeight);
}

int main() {
    Graph* graph = createGraph(V, E);
    generateRandomGraph(graph);

    kruskalMST(graph);

    free(graph->edges);
    free(graph);

    return 0;
}

